package class20;

import java.util.Scanner;

/**
 * @author YZY
 * @since 2022/8/20 16:01
 * <a href="https://www.nowcoder.com/questionTerminal/c45704a41617402fb5c34a1778bb2645">[编程题]象棋中马的跳法</a>
 * 自行搜索或者想象一个象棋的棋盘，
 * 然后把整个棋盘放入第一象限，棋盘的最左下角是(0,0)位置
 * 那么整个棋盘就是横坐标上9条线、纵坐标上10条线的区域
 * 给你三个 参数 x，y，k
 * 返回“马”从(0,0)位置出发，必须走k步
 * 最后落在(x,y)上的方法数有多少种?
 */
public class Code02_HorseJump {

    // 暴力尝试
    public static int jump1(int x, int y, int k) {
        return process1(0, 0, k, x, y);
    }

    public static int process1(int tx, int ty, int rest, int x, int y) {
        if (x < 0 || x > 9 || y < 0 || y > 8) {
            return 0;
        }
        if (rest == 0) {
            return (x == tx && y == ty) ? 1 : 0;
        }
        int way = 0;
        way += process1(tx, ty, rest - 1, x + 1, y + 2);  // (+1,+2)
        way += process1(tx, ty, rest - 1, x + 2, y + 1);  // (+2,+1)
        way += process1(tx, ty, rest - 1, x + 2, y - 1);  // (+2,-1)
        way += process1(tx, ty, rest - 1, x + 1, y - 2);  // (+1,-2)
        way += process1(tx, ty, rest - 1, x - 1, y - 2);  // (-1,-2)
        way += process1(tx, ty, rest - 1, x - 2, y - 1);  // (-2,-1)
        way += process1(tx, ty, rest - 1, x - 2, y + 1);  // (-2,+1)
        way += process1(tx, ty, rest - 1, x - 1, y + 2);  // (-1,+2)
        return way;
    }

    // 记忆化搜索
    public static int jump2(int x, int y, int k) {
        int[][][] dp = new int[10][9][k + 1];
        return process2(0, 0, k, x, y, dp);
    }

    public static int process2(int tx, int ty, int rest, int x, int y, int[][][] dp) {
        if (x < 0 || x > 9 || y < 0 || y > 8) {
            return 0;
        }
        if (dp[x][y][rest] != 0) {
            return dp[x][y][rest];
        }
        if (rest == 0) {
            return (x == tx && y == ty) ? 1 : 0;
        }
        int way = 0;
        way += process2(tx, ty, rest - 1, x + 1, y + 2, dp);  // (+1,+2)
        way += process2(tx, ty, rest - 1, x + 2, y + 1, dp);  // (+2,+1)
        way += process2(tx, ty, rest - 1, x + 2, y - 1, dp);  // (+2,-1)
        way += process2(tx, ty, rest - 1, x + 1, y - 2, dp);  // (+1,-2)
        way += process2(tx, ty, rest - 1, x - 1, y - 2, dp);  // (-1,-2)
        way += process2(tx, ty, rest - 1, x - 2, y - 1, dp);  // (-2,-1)
        way += process2(tx, ty, rest - 1, x - 2, y + 1, dp);  // (-2,+1)
        way += process2(tx, ty, rest - 1, x - 1, y + 2, dp);  // (-1,+2)
        return dp[x][y][rest] = way;
    }

    // 动态规划
    public static int jump3(int tx, int ty, int k) {
        int[][][] dp = new int[10][9][k + 1];
        dp[tx][ty][0] = 1;
        for (int rest = 1; rest <= k; ++rest) {
            for (int x = 0; x < 10; ++x) {
                for (int y = 0; y < 9; ++y) {
                    int way = 0;
                    way += pick(dp, x + 1, y + 2, rest - 1);  // (+1,+2)
                    way += pick(dp, x + 2, y + 1, rest - 1);  // (+2,+1)
                    way += pick(dp, x + 2, y - 1, rest - 1);  // (+2,-1)
                    way += pick(dp, x + 1, y - 2, rest - 1);  // (+1,-2)
                    way += pick(dp, x - 1, y - 2, rest - 1);  // (-1,-2)
                    way += pick(dp, x - 2, y - 1, rest - 1);  // (-2,-1)
                    way += pick(dp, x - 2, y + 1, rest - 1);  // (-2,+1)
                    way += pick(dp, x - 1, y + 2, rest - 1);  // (-1,+2)
                    dp[x][y][rest] = way;
                }
            }
        }
        return dp[0][0][k];
    }

    // 防越界
    private static int pick(int[][][] dp, int x, int y, int k) {
        if (x < 0 || x > 9 || y < 0 || y > 8) {
            return 0;
        }
        return dp[x][y][k];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] line = scanner.nextLine().split(" ");
        int x = Integer.parseInt(line[0]);
        int y = Integer.parseInt(line[1]);
        int k = Integer.parseInt(line[2]);
        System.out.println(jump1(x, y, k));
        System.out.println(jump2(x, y, k));
        System.out.println(jump3(x, y, k));
    }

}
